package 快排;

import java.util.PriorityQueue;
import java.util.Random;

/**
 * @Date 2024/10/8 15:12
 * @description: 找出第K大元素
 * .
 * @Author LittleNight
 */
public class likou215 {


    // 快排
    public int findKthLargest(int[] nums, int k) {
        return qsort(nums, 0, nums.length - 1, k);
    }
    public int qsort(int[] nums, int l, int r, int k) {
        if(l >= r) return nums[l];
        // 1. 随机选择元素, 数组分三块
        int key = nums[new Random().nextInt(r - l + 1) + l];
        int left = l - 1, right = r + 1, i = l;
        while(i < right) {
            if(nums[i] < key) swap(nums, ++left, i++);
            else if(nums[i] == key) i++;
            else swap(nums, --right, i);
        }
        // 去两边查找[l, left][left + 1, right - 1][right, r]
        int c = r - right + 1, b = right-1-(left+1)+1;
        if(c >= k) return qsort(nums, right, r, k); // 记得这里有 return
        else if(b + c >= k) return key;
        else return qsort(nums, l, left, k - b- c); // 记得这里有return
    }
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    // 堆排序
    public int findKthLargest22(int[] nums, int k) {
        // 创建一个最小堆，用于存储当前遍历到的最大的k个数
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        // 遍历数组的前k个元素，将它们加入最小堆中
        for(int i = 0; i < nums.length; i++){
            heap.offer(nums[i]);
            if(heap.size() > k) heap.poll();
        }
        // 堆顶元素即为第k大的元素，返回它
        return heap.peek();
    }

}
